﻿using System;

namespace SingleNumber
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            int[] arr1 = new int[] {2,2,1};
            int[] arr2 = new int[] {4,1,2,1,2};
            int[] arr3 = new int[] {1,0,1};
            int[] arr4 = new int[] {-316,615,597,-926,-596,467,-43,-99,188,-945,-481,19,308,129,-205,145,948,886,-318,-345,902,-585,422,969,-381,62,-568,-594,713,-399,-744,562,661,-962,-997,632,114,782,-591,-232,2,295,-216,553,155,175,804,-892,-567,247,301,-886,-736,-645,372,-711,-729,-551,998,-858,-2,85,-942,-334,912,156,-679,228,668,104,-558,516,443,-395,-829,-291,505,-740,799,-28,346,-394,427,-102,-314,267,137,626,-109,106,920,-5,811,305,-878,698,45,-943,377,425,394,-427,-200,-938,218,753,-360,852,-166,-121,376,644,-195,-214,908,108,-237,-906,501,285,362,-633,879,496,406,-239,139,-584,-960,341,-949,-881,-174,859,-482,-852,-87,-83,987,-747,283,-731,780,98,448,380,639,-690,131,922,931,-255,383,-739,413,532,477,300,-958,976,896,752,-271,938,-446,-374,273,730,720,11,-325,-643,622,475,-727,368,664,-955,174,801,204,798,288,-684,-100,968,-6,456,345,-769,-900,-59,-575,918,824,307,714,789,-491,-574,558,-987,-189,642,-35,-501,-251,-473,-53,820,-535,70,-283,641,196,582,-348,574,-805,781,869,-508,-751,-995,522,438,-125,-266,14,117,-204,-470,-759,324,937,-224,34,-676,486,663,884,490,-503,189,457,-132,95,46,-649,-944,-717,329,-493,-813,612,-854,-793,-847,894,-707,637,50,974,602,728,-367,209,147,-295,-838,895,-928,-794,577,-421,520,-702,-451,-436,-889,-957,-66,124,-154,-230,571,719,635,-644,230,389,303,-869,365,298,-629,-263,-456,-172,653,-183,-52,-306,183,-843,-663,791,-410,-284,539,-192,901,-426,140,386,-642,756,222,-186,-823,-346,-502,-384,-600,-116,100,275,813,-593,878,234,-115,-454,497,-775,-244,-640,592,-81,-603,864,-554,167,-732,783,-865,-550,-524,111,-547,-29,-770,-177,794,960,542,-857,399,-627,565,489,703,25,-64,557,-988,460,412,498,-920,688,-15,627,335,-316,615,597,-926,-596,467,-43,-99,188,-945,-481,19,308,129,-205,145,948,886,-318,-345,902,-585,422,969,-381,62,-568,-594,713,-399,-744,562,661,-962,-997,632,114,782,-591,-232,2,295,-216,553,155,175,804,-892,-567,247,301,-886,-736,-645,372,-711,-729,-551,998,-858,-2,85,-942,-334,912,156,-679,228,668,104,-558,516,443,-395,-829,-291,505,-740,799,-28,346,-394,427,-102,-314,267,137,626,-109,106,920,-5,811,305,-878,698,45,-943,377,425,394,-427,-200,-938,218,753,-360,852,-166,-121,376,644,-195,-214,908,108,-237,-906,501,285,362,-633,879,496,406,-239,139,-584,-960,341,-949,-881,-174,859,-482,-852,-87,-83,987,-747,283,-731,780,98,448,380,639,-690,131,922,931,-255,383,-739,413,532,477,300,-958,976,896,752,-271,938,-446,-374,273,730,720,11,-325,-643,622,475,-727,368,664,-955,174,801,204,798,288,-684,-100,968,-6,456,345,-769,-900,-59,-575,918,824,307,714,789,-491,-574,558,-987,-189,642,-35,-501,-251,-473,-53,820,-535,70,-283,641,196,582,-348,574,-805,781,869,-508,-751,-995,522,438,-125,-266,14,117,-204,-470,-759,324,937,-224,34,-676,486,663,884,490,-503,189,457,-132,95,46,-649,-944,-717,329,-493,-813,612,-854,-793,-847,894,-707,637,50,974,602,728,-367,209,147,-295,-838,895,-928,-794,577,-421,520,-702,-451,-436,-889,-957,-66,124,-154,-230,571,719,635,-644,230,389,303,-869,365,298,-629,-263,-456,-172,653,-183,-52,-306,183,-843,-663,791,-410,-284,539,-192,901,-426,140,386,-642,756,222,-186,-823,-346,-502,-384,-600,-116,100,275,813,-593,878,234,-115,-454,497,-775,-244,-640,592,-81,-603,864,-554,167,-732,783,-865,-550,-524,111,-547,-29,-770,-177,794,960,542,-857,399,-627,565,489,703,25,-64,557,-988,460,412,498,-920,688,-15,627,335,458};
            System.Console.WriteLine(SingleNumber(arr1));
            System.Console.WriteLine(SingleNumber(arr2));
            System.Console.WriteLine(SingleNumber(arr3));
            System.Console.WriteLine(SingleNumber(arr4));

            System.Console.WriteLine(SingleNumber2(arr1));
            System.Console.WriteLine(SingleNumber2(arr2));
            System.Console.WriteLine(SingleNumber2(arr3));
            System.Console.WriteLine(SingleNumber2(arr4));
        }

        /*
        给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

        说明：

        你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

        示例 1:
        输入: [2,2,1]
        输出: 1

        示例 2:
        输入: [4,1,2,1,2]
        输出: 4

        作者：力扣 (LeetCode)
        链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x21ib6/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
        */
        public static int SingleNumber(int[] nums)
        {
            for (int i = 0; i < nums.Length; i++)
            {
                bool exists = false;
                for (int j = 0; j < nums.Length; j++)
                {
                    if(i == j)
                        continue;
                    // System.Console.WriteLine($"nums[{i}]: {nums[i]} ==> nums[{j}]:{nums[j]}");
                    if(nums[i] == nums[j])
                    {
                        exists = false;
                        break;
                    }
                    exists = true;
                }
                if(exists)
                {
                    return nums[i];
                }
            }
            return nums[0];
        }

        public static int SingleNumber2(int[] nums)
        {
            int num = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                num ^= nums[i];
            }
            return num;
        }
    }
}
